//https://leetcode.cn/problems/find-elements-in-a-contaminated-binary-tree/submissions/511002393/?envType=daily-question&envId=2024-03-12


class FindElements {
public:
vector<int> ans;
    FindElements(TreeNode* root) {
        //层序遍历
        root->val = 0;
        ans.push_back(0);
        queue<TreeNode*> q;
        q.push(root);
        while(!q.empty())
        {
            int n = q.size();
            for(int i = 0;i<n;++i)
            {
                TreeNode* tmp = q.front();
                q.pop();
                if(tmp->left)
                {
                    tmp->left->val = tmp->val*2+1; 
                    ans.push_back(tmp->left->val);
                    q.push(tmp->left);
                }
                if(tmp->right)
                {
                    tmp->right->val = tmp->val*2+2;
                    ans.push_back(tmp->right->val);
                    q.push(tmp->right);
                }
            }
        }
    }
    
    bool find(int target) {
        for(auto x:ans)
        {
            if(x == target) return true;
        }
        return false;
    }
};